// 给定一个链表的头节点head，删除链表的倒数第n个节点，并返回链表的头节点

// 思路
// 常规思路，先求出链表长度，然后再遍历到对应位置，删除位置上的节点
// 如果一次遍历的话，使用快慢指针，让快指针先走n步，然后再快慢指针同时走，这样
// 当快指针到达链表末尾的时候，慢指针刚好到了倒数第n个节点位置，将该位置节点删除即可

// 时间复杂度：O(n)
// 空间复杂度：O(1)
const { ListNode, LinkedList } = require('../../1. 链表基础/1. 建立线性链表')
function removeNthFromEnd(head, n) {
    let newHead = new ListNode(0, head)
    let fast = head
    let slow = newHead
    while (n--) {
        fast = fast.next
        // n -= 1
    }
    while (fast) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return newHead.next
}

let list = new LinkedList([2, 5, 1, 7, 3, 9])
let res = removeNthFromEnd(list.head, 2)
console.log(res);